package com.conjane.algo.array_list;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 从数组中去除重复的数据
 */
public class RemoveDuplicateNumberInArray {

//    public static int[] removeDuplicateNumber(int[] array){
//        Arrays.sort(array);
//        int[] result = new int[array.length];
//        int previous = array[0];
//        result[0] = previous;
//
//        for (int i = 1; i < array.length; i++) {
//            int ch = array[i];
//            if (previous != ch) {
//                result[i] = ch;
//            }
//            previous = ch;
//        }
//        return result;
//    }

    public static int[] removeDuplicateNumber(int[] array){
        Set<Integer> set = new HashSet<>();
        int[] result = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if (!set.contains(array[i])){
                set.add(array[i]);
                result[i] = array[i];
            }
        }
        return result;
    }

    /**
     * 不使用额外空间，在原来数组上遍历数据
     * @param array
     * @return
     */
    public static int removeDuplicate(int[] array){
        int length = array.length;
        for (int i = 0; i < length - 1; ) {
            if (array[i] != array[i + 1]){
                i++;
            }else {
                for (int j = i + 1; j < length - 1; j++) {
                    array[j] = array[j + 1];
                }
                length--;
            }
        }
        return length;
    }

    /**
     * 最优解：双指针解法
     * 1：定义两个指针，分别指向目标位和待移动位，目标位为0，待移动位为1
     * 2：比较两个元素
     *  比较相等：目标位不变，带移动位加1
     *  比较不相等：目标位加1，待移动位元素移动到目标位上，待移动位加1
     * @param array
     * @return
     */
    public static int removeDuplicatePlus(int[] array){
        // 定义两个指针，分别指向目标位和待移动元素位
        int target = 0;
        for (int i = 1; i < array.length; i++) { // i为待移动指针位
            // 比较两个对应的数据
            if (array[target] != array[i]){
                // 不相等，则把目标位后移
                if (++target != i){
                    array[target] = array[i];
                }
            }

        }
        return target + 1;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,4,5,3,6,5,3,8,0,1};
        int[] ints = removeDuplicateNumber(array);
        System.out.println(Arrays.toString(ints));

        int[] sortArray = new int[]{1,1,1,3,3,4,5,6,7,7,7,7,8,8,9};
        System.out.println(removeDuplicatePlus(sortArray));
    }
}
